package com.hotkid.ceo.jetpack.myjetpackmvvm.base

import java.util.*

/**
 * ClassName:Test
 * Package:com.hotkid.ceo.jetpack.myjetpackmvvm.base
 * Description:
 * @date:2021/3/19 4:52 PM
 * @author:774169396@qq.com
 */
class Test {
    /***
     * 2数之和指定值
     */


    open fun method(sums: IntArray, sum: Int): IntArray? {
        var compleemnt:Int
        val map= hashMapOf<Int, Int>()
        for (i in sums.indices){
            compleemnt=sum-sums[i]
            if (map.containsKey(compleemnt)){
                return intArrayOf(map[compleemnt]!!.toInt(), i)
            }

            map[sums[i]]=i
        }
        return intArrayOf()
    }

    /**
     * 返回第K个最大值
     */

    fun findKthLargest(nums: IntArray, k: Int): Int {
         if (nums.isEmpty())return 0
        //1.冒泡排序
//        for (i in nums.indices){
//            for (j in nums.indices-i-1){
//                if (nums[j+1]<nums[j]){
//                    var temp=nums[j+1]
//                    nums[j+1]=nums[j]
//                    nums[j]=temp
//                }
//            }
//        }
        /**
         * 选择排序
         */
//        for (i in nums.indices){
//            var minIndex=i
//            for ( j in i until  nums.size){
//                if (nums[j]<nums[minIndex]){
//                    minIndex=j
//                }
//
//                var temp=nums[minIndex]
//                nums[minIndex]=nums[i]
//                nums[i]=temp
//            }
//        }
      //插入排序
//
//        var curent:Int
//        for (i in 0 until nums.size-1){
//            curent=nums[i+1]
//            var preIndex=i
//            while (preIndex>=0&&curent<nums[preIndex]){
//                nums[preIndex+1]=nums[preIndex]
//                preIndex--
//            }
//            nums[preIndex+1]=curent
//        }
//          val len = array.size
//        var temp: Int
//        var gap = len / 2
//        while (gap > 0) {
//            for (i in gap until len) {
//                temp = array[i]
//                var preIndex = i - gap
//                while (preIndex >= 0 && array[preIndex] > temp) {
//                    array[preIndex + gap] = array[preIndex]
//                    preIndex -= gap
//                }
//                array[preIndex + gap] = temp
//            }
//            gap /= 2
//        }
        //希尔排序

//        val len=nums.size
//        var temp:Int
//        var gap=len/2
//        while (gap>0){
//            for (i in gap until len){
//                temp=nums[i]
//                var preIndex=i-gap
//                while (preIndex>=0&&nums[preIndex]>temp){
//                    nums[preIndex+gap]=nums[preIndex]
//                    preIndex-=gap
//                }
//                nums[preIndex+gap]=temp
//            }
//            gap/=2
//        }

//        Arrays.sort(nums)
         //api进行排序的
//          nums.sort()
        return nums[nums.size - k]
    }

    /**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    fun bubbleSort(array: IntArray): IntArray? {
        if (array.isEmpty()) return array
        for (i in array.indices) for (j in 0 until array.size - 1 - i) if (array[j + 1] < array[j]) {
            val temp = array[j + 1]
            array[j + 1] = array[j]
            array[j] = temp
        }
        return array
    }


    /**
     * 选择排序
     * @param array
     * @return
     */
    fun selectionSort(array: IntArray): IntArray? {
        if (array.size == 0) return array
        for (i in array.indices) {
            var minIndex = i
            for (j in i until array.size) {
                if (array[j] < array[minIndex]) //找到最小的数
                    minIndex = j //将最小数的索引保存
            }
            val temp = array[minIndex]
            array[minIndex] = array[i]
            array[i] = temp
        }
        return array
    }

    /**
     * 插入排序
     * @param array
     * @return
     */
    fun insertionSort(array: IntArray): IntArray? {
        if (array.isEmpty()) return array
        var current: Int
        for (i in 0 until array.size - 1) {
            current = array[i + 1]
            var preIndex = i
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex]
                preIndex--
            }
            array[preIndex + 1] = current
        }
        return array
    }


    /**
     * 希尔排序
     *
     * @param array
     * @return
     */
    fun ShellSort(array: IntArray): IntArray? {
        val len = array.size
        var temp: Int
        var gap = len / 2
        while (gap > 0) {
            for (i in gap until len) {
                temp = array[i]
                var preIndex = i - gap
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex]
                    preIndex -= gap
                }
                array[preIndex + gap] = temp
            }
            gap /= 2
        }
        return array
    }


    /**
     * 归并排序
     *
     * @param array
     * @return
     */
    fun MergeSort(array: IntArray): IntArray {
        if (array.size < 2) return array
        val mid = array.size / 2
        val left: IntArray = array.copyOfRange(0, mid)
        val right: IntArray = array.copyOfRange(mid, array.size)
        return merge(MergeSort(left), MergeSort(right))
    }

    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    private fun merge(left: IntArray, right: IntArray): IntArray {
        val result = IntArray(left.size + right.size)
        var index = 0
        var i = 0
        var j = 0
        while (index < result.size) {
            when {
                i >= left.size -> result[index] = right[j++]
                j >= right.size -> result[index] = left[i++]
                left[i] > right[j] -> result[index] = right[j++]
                else -> result[index] = left[i++]
            }
            index++
        }
        return result
    }


    /**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    fun QuickSort(array: IntArray, start: Int, end: Int): IntArray? {
        if (array.isEmpty() || start < 0 || end >= array.size || start > end) return null
        val smallIndex = partition(array, start, end)
        if (smallIndex > start) QuickSort(array, start, smallIndex - 1)
        if (smallIndex < end) QuickSort(array, smallIndex + 1, end)
        return array
    }

    /**
     * 快速排序算法——partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    fun partition(array: IntArray, start: Int, end: Int): Int {
        val pivot = (start + Math.random() * (end - start + 1)).toInt()
        var smallIndex = start - 1
        swap(array, pivot, end)
        for (i in start..end) if (array[i] <= array[end]) {
            smallIndex++
            if (i > smallIndex) swap(array, i, smallIndex)
        }
        return smallIndex
    }

    /**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    fun swap(array: IntArray, i: Int, j: Int) {
        val temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }


    //声明全局变量，用于记录数组array的长度；
    var len = 0

    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    fun HeapSort(array: IntArray): IntArray? {
        len = array.size
        if (len < 1) return array
        //1.构建一个最大堆
        buildMaxHeap(array)
        //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1)
            len--
            adjustHeap(array, 0)
        }
        return array
    }

    /**
     * 建立最大堆
     *
     * @param array
     */
    fun buildMaxHeap(array: IntArray) {
        //从最后一个非叶子节点开始向上构造最大堆
        //for循环这样写会更好一点：i的左子树和右子树分别2i+1和2(i+1)
        for (i in len / 2 - 1 downTo 0) {
            adjustHeap(array, i)
        }
    }

    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    fun adjustHeap(array: IntArray, i: Int) {
        var maxIndex = i
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 < len && array[i * 2] > array[maxIndex]) maxIndex = i * 2 + 1
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) maxIndex = i * 2 + 2
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i)
            adjustHeap(array, maxIndex)
        }
    }



}